/*
 * @lc app=leetcode.cn id=138 lang=javascript
 *
 * [138] 复制带随机指针的链表
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
  if (head === null) return head;

  // 复制节点,每个原节点后都有1个复制的新节点
  let p = head;
  while (p) {
    let node = new Node(p.val, p.next, p.random);
    p.next = node;
    p = node.next;
  }

  // 更新复制节点的random指针
  p = head.next;
  while (p) {
    p.random = p.random ? p.random.next : null;
    // 最后一个节点判断
    p = p.next ? p.next.next : null;
  }

  // 将复制节点取出来
  const newHead = head.next;
  let q = head.next;
  p = head;
  while (q) {
    p.next = q.next;
    p = p.next;
    // 最后一个节点判断
    q.next = p ? p.next : null;
    q = q.next;
  }
  return newHead;
};
// @lc code=end
